In computer graphics, various methods have been developed for rendering a three-dimensional scene. One rendering method is ray tracing. Ray tracing is a global illumination rendering method that is able to render advanced visual effects such as reflection, refraction, and shadows. Ray tracing works by modeling and tracing the paths of individual rays of light as those rays make contact with objects within a three-dimensional scene. Ray tracing is thus capable of rendering a more realistic view of a scene than other rendering methods that are incapable of modeling reflection, refraction, and shadows.
In ray tracing, a single real-world item in a three-dimensional scene is typically modeled as multiple objects. Typical objects include points, lines, two-dimensional shapes, and three-dimensional shapes. For example, one commonly used object is a triangle, and a single real-world item in a three-dimensional scene can be modeled, for example, as thousands or millions of triangles. Given a real-world item in a three-dimensional scene that is modeled as thousands or millions of objects, the main objective of ray tracing the item is to determine how a given number of rays intersect with the objects that make up that item in the three-dimensional scene. Because of the high number of objects in even relatively basic three-dimensional scenes, simply testing each the ray against each object is very inefficient. Often ray tracing methods reduce the number of these intersection tests by using acceleration data structures to accelerate ray tracing. One such data structure is a grid.
A grid is a data structure that includes a plurality of cells that each defines a volume of three-dimensional space. Grids enable ray tracing applications to perform a relatively low-cost test to determine if a ray is in the general vicinity of an object before having to perform a relatively high-cost test to determine if the ray intersects with the object. In the event that the relatively low-cost test determines that the ray is not in the general vicinity of the object, the relatively high-cost test can be avoided altogether, thus resulting in a lower overall cost of ray tracing a scene.
For example, a grid can be populated with the objects that make up a three-dimensional scene. Once the grid is populated by spatially partitioning the objects into the cells of the grid, each object in the scene corresponds either to a single cell (where the object is bounded by the single cell) or to a group of cells (where the object is bounded by the group of cells).
Using this grid, where an object is bounded by a single cell, a ray tracing method can first perform a relatively low-cost test for an intersection between a ray and the cell. Where the ray does not intersect the cell, the ray tracing method can avoid a relatively high-cost test for an intersection between the ray and the object, since it is known that where the ray does not intersect with a cell the ray will also not intersect with any objects bounded by the cell. Similarly, where an object is bounded by a group of cells, a ray tracing method can first perform relatively low-cost tests for intersection between a ray and each cell in the group of cells. Where the ray does not intersect any of the cells in the group of cells, the ray tracing method can avoid a relatively high-cost test for an intersection between the ray and the object, since it is known that where a ray does not intersect with a group of cells, the ray will also not intersect with any objects bounded by the group of cells. A grid can thus be used to lower the number of relatively costly intersection tests between a ray and the objects in a scene.
Unfortunately however, even using a grid, a typical ray tracing method may nevertheless remain very costly in terms of time and processing resources, due in part to the time and processing resources that are consumed during the population of the grid with the large number of objects in a three-dimension scene. For example, as noted above, a single real-world item in a typical scene may be modeled by thousands or millions of objects. Populating a grid with thousands or millions of objects in order to ray trace a single frame of a scene can make rendering the scene very costly in terms of time and processing resources compared to other rendering methods. The time it takes to populate and repopulate a grid can be excessively slow to make ray tracing using a grid a viable alternative to other rendering methods, especially for applications that make use of dynamically changing scenes with multiple frames per second, such as simulation and game applications.